class Solution(object):
    def findShortestSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums_info = {}
        max_count = 0
        min_len = 0
        for i, num in enumerate(nums):
            if num not in nums_info:
                nums_info[num] = [1, i, i]
            else:
                nums_info[num][0] += 1
                nums_info[num][2] = i
            occur_count = nums_info[num][0]
            occur_len = nums_info[num][2] - nums_info[num][1] + 1
            if occur_count > max_count:
                max_count = occur_count
                min_len = occur_len
            elif occur_count == max_count:
                min_len = min(min_len, occur_len)
        return min_len
if __name__ == '__main__':
    nums = [1, 2, 2, 3, 1]
    print(Solution().findShortestSubArray(nums))
# 思路：
# 1. 遍历数组，统计每个数字出现的次数、首次出现的位置、最后一次出现的位置
# 2. 记录最大出现次数和最小长度
# 3. 遍历数组，如果当前数字出现次数等于最大出现次数，则更新最小长度
# 4. 返回最小长度
# 时间复杂度：O(n)
# 空间复杂度：O(n)